package codeTop;

public class circle {
    long func(int n){
        if (n % 2 == 1) {
            return 0;
        }
        int half = n/2;
        long res = combination(half,n);;
        for (int i = 5; i <= half; i+=5) {
            res+=2*combination(half-i,n);
        }
        return res;
    }
    public static long func1(int n) {
        long[][] dp = new long[n+1][10];
        dp[0][0] = 1;
        for (int i = 1; i <=n ; i++) {
            for (int j = 0; j < 10; j++) {
                dp[i][j] = dp[i-1][(j-1+10)%10]+dp[i-1][(j+1)%10];
            }
        }
        return dp[n][0];
    }
    long combination(int k,int n){
        long res = 1;
        if (k > n - k) {
            k = n-k;
        }
        for (int i = 0; i <k ; i++) {
            res*=(n-i);
        }
        for (int i = 1; i <=k ; i++) {
            res/=i;
        }
        return res;
    }

    public static void main(String[] args) {
        circle circle = new circle();
        System.out.println(circle.func(20));
        System.out.println(circle.func1(20));
    }
}
